package com.yq.leetcodeOld;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName Solution42
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/3/23 13:52
 * @Version 1.0
 */
public class Solution42 {
    public static void main(String[] args) {
       int[] height = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
       trap(height);
    }
    public static int trap(int[] height){
        int ans=0;
        Deque<Integer> stack=new LinkedList<>();
        int n=height.length;
        for(int i=0;i<n;++i){
            while (!stack.isEmpty() && height[i]>height[stack.peek()]){
                int top=stack.pop();
                if(stack.isEmpty()){break;}
                int left=stack.peek();
                int currWidth=i-left-1;
                int currHeight=Math.min(height[left],height[i])-height[top];
                ans+=currHeight*currWidth;
            }
            stack.push(i);
        }
        System.out.println(ans);

        return ans;
        /**
         int ans = 0;
         Deque<Integer> stack = new LinkedList<Integer>();
         int n = height.length;
         for (int i = 0; i < n; ++i) {
         while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
         int top = stack.pop();
         if (stack.isEmpty()) {
         break;
         }
         int left = stack.peek();
         int currWidth = i - left - 1;
         int currHeight = Math.min(height[left], height[i]) - height[top];
         ans += currWidth * currHeight;
         }
         stack.push(i);
         }
         return ans;


         */
    }
}
